/*
 * step1or2.cpp
 *
 *  Created on: Aug 20, 2012
 *      Author: xkq
 */

#include <iostream>
using namespace std;

int step1or2(int n){
	if(n==0) return 0;
	if(n==1) return 1;
	if(n==2) return 2;
	return step1or2(n-2) + step1or2(n-1);
}

int steps[100];

int step1or2_sec(int n){
	if(n==0) return 0;
	if(n==1) return 1;
	if(n==2) return 2;
	if(steps[n]==-1)
		steps[n]=step1or2_sec(n-1)+step1or2_sec(n-2);
	return steps[n];
}

int main(){
	for(int i=0;i<100;i++)
		steps[i]=-1;
	cout<<step1or2_sec(3)<<endl;
	return 0;
}
